/**
 * Created by IntelliJ IDEA.
 * User: Alexander Fedulin
 * Date: 01.11.11
 * Time: 15:37
 * To change this template use File | Settings | File Templates.
 */


import java.io.*;
import java.nio.channels.FileChannel;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Restaurant {

    private String problem_input = "restaurant.in";
    private String problem_output = "restaurant.out";
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter out;

    String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }
    int N, M, K;

    void load() throws IOException
    {
        N = nextInt();
        M = nextInt();
        K = nextInt();
    }
    final long mod = 1000000007;
    long _x, _y;

    void extGcd(long a, long b)
    {
        if (b == 0)
        {
            _x = 1;
            _y = 0;
        }
        else
        {
            long x, y;
            extGcd(b, a % b);
            x = _y;
            y = _x - (a / b) * _y;
            _x = x;
            _y = y;
        }
    }
    long invMod(long a)
    {
        extGcd(a, mod);
        _x %= mod;
        _x += mod;
        _x %= mod;
        return _x;
    }
    long fastPowMod(long a, int b)
    {
        long d = 1;
        while (b > 0)
        {
            if ((b & 1) > 0)
            {
                d = d * a;
                d %= mod;
            }
            a = a * a;
            a %= mod;
            b >>= 1;
        }
        return d;
    }
    long f[][] = new long[1001][1001];
    long F(int n, int k)
    {
        if (k == 0)
            return 0;
        if (f[n][k] != -1) return f[n][k];
        f[n][k] = 0;
        long C = 1;
        long d = fastPowMod(k, N);
        for (int j = 0; j < k; j++)
        {
            if (j % 2 == 0)
                f[n][k] += (fastPowMod(k - j, N) * C) % mod;
            else f[n][k] -= (fastPowMod(k - j, N) * C) % mod;
            C *= (k - j);
            C %= mod;
            C *= invMod(j + 1);
            C %= mod;
        }
        if (f[n][k] < 0) f[n][k] += mod;
        return f[n][k];
    }
    void solve() {
        long res = 0;
        long C = M % mod;
        for (int k = 1; k <= K; k++)
        {
            res += (C * F(N, k)) % mod;
         //   System.err.println(C + "*" + F(N, k) + "=" + (C * F(N, k)));
            if (res >= mod) res -= mod;
            if (res < 0) res += mod;
            C *= (M - k);
            C %= mod;
            C *= invMod(k + 1);
            C %= mod;
        }
        out.println(res);
    }

    void run() {
        try {
            boolean online_judge = System.getProperty("ONLINE_JUDGE") != null;
            if (online_judge) {
                br = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            } else {
                br = new BufferedReader(new FileReader(problem_input));
                out = new PrintWriter(new FileWriter(problem_output));
            }
            int T = nextInt();
            for (int i = 0; i <= 1000; i++)
                Arrays.fill(f[i], -1);
            for (int i = 0; i < T; i++)
            {
             load();
             solve();
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(42);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    public static void main(String args[]) {
        new Restaurant().run();
    }
}
